package bite;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-06-08
 * Time:16:34
 */
public class Day32_2 {
    public static void main(String[] args) {
        List<Long> list = new ArrayList<>();
        //记录是什么时候超过六位数的
        int count = -1;
        long first = 1l;
        long second = 2l;
        long three = 0;
        list.add(first);
        list.add(second);
        for (int i = 0; i <= 100000; i++) {
            three = first + second;
            if(count == -1 && three >= 1000000){
                count = i + 1;
            }
            three = three  % 1000000;
            list.add(three);
            first = second;
            second = three;
        }
        Scanner input = new Scanner(System.in);
        while(input.hasNextInt()){

            int num = input.nextInt();
            if(num < count){
                System.out.printf("%d\n",list.get(num - 1));
            }else{
                System.out.printf("%06d\n",list.get(num - 1));
            }


        }
    }
    public static void main1(String[] args) {
        List<Long> list = new ArrayList<>();
        long first = 1l;
        long second = 2l;
        long three = 0;
        list.add(first);
        list.add(second);
        for (int i = 0; i <= 100000; i++) {
            three = (first + second) % 1000000;
            list.add(three);
            first = second;
            second = three;
        }
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int num = input.nextInt();
            System.out.printf((num<25 ? "%d\n":"%06d\n"), list.get(num - 1));
        }
    }

}
